package com.lw.leetcode.node;

import com.lw.leetcode.linked.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liw
 * @Date 2021/4/21 9:25
 * @Version 1.0
 */
public class Partition {
    public static void main(String[] args) {
//        ListNode a = new ListNode(1);
//        ListNode b = new ListNode(4);
//        ListNode c = new ListNode(3);
//        ListNode d = new ListNode(2);
//        ListNode e = new ListNode(5);
//        ListNode f = new ListNode(2);
//        a.next = b;
//        b.next = c;
//        c.next = d;
//        d.next = e;
//        e.next = f;
//        ListNode partition = new Partition().partition(a, 3);
//        System.out.println(partition);

        List<List<String>> partition = new Partition().partition("aabbaa");
        System.out.println(partition);
    }

    // [,,,["aa","b","b","a","a"],["aa","b","b","aa"],["aa","bb","a","a"],]
    // [, [aa, b, b, a, a], , [aa, bb, a, a],   [aa, b, b, aa],   ]

    public List<List<String>> partition(String s) {
        List<List<String>> all = new ArrayList<>();
        int length = s.length();
        List<String> list = new ArrayList<>();
        list.add(s.substring(0, 1));
        all.add(list);
        for (int i = 1; i < length; i++) {
            String str = String.valueOf(s.charAt(i));
            List<List<String>> copy = new ArrayList<>();
            for (List<String> a : all) {
                int size = a.size();
                String last1 = a.get(size - 1);
                if (last1.equals(str)) {
                    list = copy(a, size - 1);
                    list.add(str + str);
                    copy.add( list);
                }
                if (size > 1) {
                    String last2 = a.get(size - 2);
                    if (last2.equals(str)) {
                        list = copy(a, size - 2);
                        list.add(str +last1 + str);
                        copy.add( list);
                    }
                }
                a.add(str);
            }
            all.addAll(copy);
        }
        return all;
    }

    private static List<String> copy (List<String> list, int limit){

        List<String> other = new ArrayList<>(limit + 1);
        for (int i = 0; i < limit; i++) {
            other.add(list.get(i));
        }
        return other;
    }


    public ListNode partition(ListNode head, int x) {
        ListNode a1 = new ListNode(0);
        ListNode a2 = a1;
        ListNode b1 = new ListNode(0);
        ListNode b2 = b1;
        while (head != null) {
            if (head.val >= x) {
                b1.next = head;
                b1 = b1.next;
            } else {
                a1.next = head;
                a1 = a1.next;
            }
            head = head.next;
        }
        b1.next = null;
        a1.next = b2.next;
        return a2.next;
    }

}
